package org.laizili.solution.nowcodertop101.list;

import org.laizili.structure.list.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=295&sfm=html&channel=nowcoder">BM10 两个链表的第一个公共结点</a>
 */
public class BM10 {
    // 双指针长度比较法
    private static class Solution {
        public int getLengthOfList(ListNode pHead) {
            ListNode p = pHead;
            int n = 0;
            while (p != null) {
                n++;
                p = p.next;
            }
            return n;
        }

        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode
                pHead2) {
            int p1 = getLengthOfList(pHead1);
            int p2 = getLengthOfList(pHead2);
            if (p1 >= p2) {
                int n = p1 - p2;
                for (int i = 0; i < n; i++) {
                    pHead1 = pHead1.next;
                }
                while ((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)) {
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
            } else {
                int n = p2 - p1;
                for (int i = 0; i < n; i++) {
                    pHead2 = pHead2.next;
                }
                while ((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)) {
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
            }
            return pHead1;
        }
    }

    //双指针连接法
    // 原理：
    //     链1： {A}_{Suffix}
    //     链2:  {B}_{Suffix}
    //        suffix代表公共结点集
    //        构造:  A_Suffix B_Suffix ，记为 list1
    //              B_Suffix A_Suffix ，记为 list2
    //        list1与list2等长，顺序遍历，即可找到第一个公共结点
    //
    private static class Solution2 {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            ListNode p1 = pHead1, p2 = pHead2;
            while (p1 != p2) {
                p1 = p1 == null ? pHead2 : p1.next;
                p2 = p2 == null ? pHead1 : p2.next;
            }
            return p1;
        }
    }

    //栈 思路
    private static class Solution3 {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            Deque<ListNode> stack1 = new ArrayDeque<>();
            Deque<ListNode> stack2 = new ArrayDeque<>();
            while (pHead1 != null) {
                stack1.push(pHead1);
                pHead1 = pHead1.next;
            }
            while (pHead2 != null) {
                stack2.push(pHead2);
                pHead2 = pHead2.next;
            }
            ListNode res = null;
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                ListNode node1 = stack1.pop();
                ListNode node2 = stack2.pop();
                if (node1 != node2) {
                    break;
                }
                res = node1;
            }
            return res;
        }
    }
}
